package com.scheuk.puzzles;

/**
 * Recursive generation of all permutations.
 *
 * Note that this provides a schema for backtracking in a
 * permutation-based problem.
 *
 * Author:  Timothy Rolfe
 */
public class RolfePermute
{
   // Can x[0..k] lead to a correct solution?
   static boolean feasible(Object[] x, int k)
   {  // Stub method --- EVERYTHING is feasible!
      return true;
   }

   static void swap(Object[] x, int j, int k)
   {  Object temp = x[j]; x[j] = x[k]; x[k] = temp;  }

   static void permute(Object[] x, int idx)
   {  int k;
      // Every step has been feasible --- this is a valid solution
      if (idx == x.length)
      {  // Processing --- for demonstration, just printing.
         for (k = 0; k < x.length; k++)
            System.out.printf("%s ", x[k]);
         System.out.println();
      }
      else
      {  Object hold;
         for (k = idx; k < x.length; k++)
         {  swap (x, idx, k);
            if (feasible(x, idx))
               permute(x, idx+1);
         }
         // The above loop has effectively done a right-shift of one
         hold = x[idx]; // Belongs at the very end.
         for (k = idx+1; k < x.length; k++)
            x[k-1] = x[k];
         x[k-1] = hold;
      }
   }
   public static void main(String[] args)
   {
      Integer[] vect = { 1, 2, 3 };
      long start = System.currentTimeMillis();
      permute(vect, 0);
      long end = System.currentTimeMillis();
      System.out.println("took " + (end - start) + " ms");
   }
}